# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
from typing import List, Optional

from python.mypackage import ListNode


class Solution:
    """
    方法：分治合并K个有序链表
        1. 将K个链表配对并将同一对中的链表合并
        2. 第一轮合并以后，K个链表被合并成了K/2个链表
        3. 重复这个过程，直到最终得到了一个链表

    Args:
        lists: List[Optional[ListNode]] - K个升序链表的头节点列表

    Returns:
        Optional[ListNode] - 合并后的升序链表的头节点

    Time: O(N*logk) - N是所有链表中元素的总和，k是链表个数。需要进行logk轮合并，每轮合并的时间复杂度是O(N)

    Space: O(logk) - 递归调用的深度是logk
    """
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists: return None
        return self.merge(lists, 0, len(lists) - 1)
    
    def merge(self, lists, l, r):
        if l == r: return lists[l]
        mid = (l + r) // 2
        l1 = self.merge(lists, l, mid)
        l2 = self.merge(lists, mid + 1, r)
        return self.mergeTwo(l1, l2)
    
    def mergeTwo(self, l1, l2):
        if not l1: return l2
        if not l2: return l1
        if l1.val < l2.val:
            l1.next = self.mergeTwo(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwo(l1, l2.next)
            return l2
        

    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        cur = dummy = ListNode()
        while list1 and list2:
            if list1.val < list2.val:
                cur.next = list1
                list1 = list1.next
            else:
                cur.next = list2
                list2 = list2.next
            cur = cur.next
        cur.next = list1 if list1 else list2
        return dummy.next
    
    """
    方法：合并K个有序链表
        使用迭代的方式，两两合并链表，直到只剩下一个链表。

    Args:
        lists: List[Optional[ListNode]] - K个升序链表的头节点列表

    Returns:
        Optional[ListNode] - 合并后的升序链表的头节点

    Time: O(N*logk) - N是所有链表中元素的总和，k是链表个数。需要进行logk轮合并，每轮合并的时间复杂度是O(N)

    Space: O(1) - 只使用了常数个变量
    """
    def mergeKLists1(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        m = len(lists)
        if m ==0:
            return None
        step = 1
        while step < m:
            for i in range(0, m - step, step * 2):
                lists[i] = self.mergeTwoLists(lists[i], lists[i + step])
            step *= 2
        return lists[0]

    
     
    
     